home *** CD-ROM | disk | FTP | other *** search
/ NeXT Education Software Sampler 1992 Fall / NeXT Education Software Sampler 1992 Fall.iso / Programming / Source / plot3d / expr.m < prev    next >
Encoding:
Text File  |  1991-07-19  |  14.1 KB  |  492 lines
  1.  
  2. # line 3 "expr.ym"
  3. /*
  4.     expr.ym
  5.  
  6.     This file defines the grammar for parsing expressions.  To fully understand
  7.     this code you will need to understand yacc.  The basic idea is that
  8.     the parse tree is built from the bottom up as larger and larger
  9.     sub-expressions are recognized by the grammar.  The nodes of the tree
  10.     are created by the alloc* functions at the end of the file.  These
  11.     functions are called by the rules of the grammar as various types of
  12.     sub-expressions are recognized.  The one entry point to this file,
  13.     _EXPParseExpression() encapsulates all the lex and yacc glue necessary
  14.     to parse an expression.
  15. */
  16.  
  17. #import <stdlib.h>
  18. #import <string.h>
  19. #import <stdio.h>
  20. #import "exprDefs.h"
  21.  
  22. static Term *allocBinaryOpTerm(char op, Term *t1, Term *t2);
  23. static Term *allocVarTerm(char *name);
  24. static Term *allocConstantTerm(float value, BOOL isInt);
  25. static Term *allocFuncTerm(char *name, TermList *args);
  26. static void addAllocedTerm(Term *t);
  27. static void yyerror(char *s);
  28. extern yylex(), yyparse();
  29.  
  30. /* globals used to build up results of the parse */
  31. static NXHashTable *ValidFuncTerms;    /* list of funcs we allow */
  32. static NXHashTable *VarTerms;        /* vars found in expression */
  33. static Term *CompleteExpr;        /* top of parse tree */
  34. static BOOL ParseError;            /* was there a parse error? */
  35. static Term **TermsAlloced;        /* terms alloced during parse */
  36. static int NumTermsAlloced;        /* #terms alloced during parse */
  37. static NXZone *ParseZone;        /* zone to allocate parse results in */
  38.  
  39. /* initial size of TermsAlloced ptr array */
  40. #define STACK_TERMS    200
  41.  
  42.  
  43. # line 46 "expr.ym"
  44. typedef union  {
  45.     Term *node;
  46.     TermList *list;
  47.     float real;
  48.     int integer;
  49.     char *string;
  50.     char character;
  51. } YYSTYPE;
  52. # define IDENTIFIER 257
  53. # define NUMBER 258
  54. # define INTEGER 259
  55. # define BADCHAR 260
  56. # define UMINUS 261
  57. #define yyclearin yychar = -1
  58. #define yyerrok yyerrflag = 0
  59. extern int yychar;
  60. extern short yyerrflag;
  61. #ifndef YYMAXDEPTH
  62. #define YYMAXDEPTH 150
  63. #endif
  64. YYSTYPE yylval, yyval;
  65. # define YYERRCODE 256
  66.  
  67. # line 121 "expr.ym"
  68.  
  69.  
  70. /*
  71.  * The main entry point into this file.  This routine sets up some globals
  72.  * and calls yyparse(), a routine generated by yacc, to do the actual parse.
  73.  * If the parse succeeds, the results are found in the globals, and are
  74.  * returned to the caller.
  75.  *
  76.  * Note because of the globals this files uses to communicate between this
  77.  * routine and the parsing guts, this is not thread safe (the yacc and lex
  78.  * internals probably aren't thread safe either).  One easy solution to this
  79.  * would be to put a mutex lock around the whole parse.
  80.  *
  81.  * If there is a parse error, since the tree is built bottom up it can be
  82.  * difficult to free the data structures allocated before the error is
  83.  * detected.  To solve this problem we keep a global buffer of pointers to
  84.  * the parse tree nodes as they are allocated.  In the event of an error
  85.  * we can then easily free them all regardless of the state of the parse tree.
  86.  * Its also very important to empty the varTerms hash table in this case, so
  87.  * it is not returned full of freed nodes.
  88.  */
  89. BOOL _EXPParseExpression(const char *text, NXHashTable *validTerms, Term **parseTree, NXHashTable *varTerms, NXZone *zone)
  90. {
  91.     int parseRet;
  92.     Term *termsAllocedStackSpace[STACK_TERMS];
  93.     int i;
  94.  
  95.     CompleteExpr = NULL;    /* set globals to prepare for parsing */
  96.     VarTerms = varTerms;
  97.     ParseError = NO;
  98.     ValidFuncTerms = validTerms;
  99.     TermsAlloced = termsAllocedStackSpace;
  100.     NumTermsAlloced = 0;
  101.     ParseZone = zone;
  102.     _EXPPrepareToScan(text);    /* sets up lex to scan the string */
  103.     parseRet = yyparse();
  104.     if (parseRet == 1 || ParseError) {
  105.     for (i = 0; i < NumTermsAlloced; i++)
  106.         _EXPFreeTerm(NULL, TermsAlloced[i]);
  107.     *parseTree = NULL;
  108.     NXEmptyHashTable(varTerms);
  109.     } else
  110.     *parseTree = CompleteExpr;
  111.     if (NumTermsAlloced > STACK_TERMS)
  112.     NXZoneFree(NXDefaultMallocZone(), TermsAlloced);
  113.     return !(parseRet == 1 || ParseError);
  114. }
  115.  
  116. /* allocates a new binary operator term */
  117. static Term *allocBinaryOpTerm(char op, Term *t1, Term *t2)
  118. {
  119.     Term *newTerm;
  120.  
  121.     newTerm = _EXPAllocTerm(ParseZone, binOpTerm, 2, t1, t2);
  122.     newTerm->data.binOp.op = op;
  123.     addAllocedTerm(newTerm);
  124.     return newTerm;
  125. }
  126.  
  127. /*
  128.  * Allocates a new variable term.  We first check to see if the variable has
  129.  * already been seen in this parse, and if so return the existing variable
  130.  * term.  Otherwise we go ahead and allocate a new one.
  131.  */
  132. static Term *allocVarTerm(char *name)
  133. {
  134.     Term *newTerm;
  135.     Term key;
  136.  
  137.     key.tag = varTerm;
  138.     key.data.var.name = name;
  139.     newTerm = NXHashGet(VarTerms, &key);
  140.     if (!newTerm) {
  141.     newTerm = _EXPAllocTerm(ParseZone, varTerm, 0);
  142.     newTerm->data.var.name = NXCopyStringBufferFromZone(name, ParseZone);
  143.     NXHashInsert(VarTerms, newTerm);
  144.     addAllocedTerm(newTerm);
  145.     }
  146.     free(name);
  147.     return newTerm;
  148. }
  149.  
  150. /* allocates a new constant term */
  151. static Term *allocConstantTerm(float value, BOOL isInt)
  152. {
  153.     Term *newTerm;
  154.  
  155.     newTerm = _EXPAllocTerm(ParseZone, constantTerm, 0);
  156.     newTerm->data.constant.val = value;
  157.     newTerm->data.constant.isInt = isInt;
  158.     addAllocedTerm(newTerm);
  159.     return newTerm;
  160. }
  161.  
  162. /*
  163.  * Allocates a new function term.  It looks up the function by name to see
  164.  * if it is one we know how to parse.  If so, it makes sure the number of
  165.  * arguments being passed is correct for the function.  If the function is
  166.  * unknown or the number of arguments is wrong, we record the fact that
  167.  * we've had a parse error in a global.
  168.  */
  169. static Term *allocFuncTerm(char *name, TermList *args)
  170. {
  171.     Term *newTerm;
  172.     Function *func;
  173.     Function key;
  174.     TermList noArgs;
  175.  
  176.     if (!args) {
  177.     args = &noArgs;
  178.     args->num = 0;
  179.     }
  180.     key.name = (char *)name;
  181.     func = NXHashGet(ValidFuncTerms, &key);
  182.     newTerm = _EXPAllocTerm(ParseZone, funcTerm, args->num);
  183.     bcopy(args->terms, newTerm->subterms, args->num * sizeof(Term *));
  184.     newTerm->data.func.type = func;
  185.     if (!func || args->num < func->minArgs ||
  186.         (args->num > func->maxArgs && func->maxArgs != -1))
  187.     ParseError = YES;
  188.     NXZoneFree(NXDefaultMallocZone(), args);
  189.     free(name);
  190.     addAllocedTerm(newTerm);
  191.     return newTerm;
  192. }
  193.  
  194. /*
  195.  * Adds a term to the list of terms that we have allocated during this parse.
  196.  * This routine allocates more space for Term pointers if necessary.  It knows
  197.  * not to free the initial buffer of these pointers, since that buffer is
  198.  * allocated on the stack by _EXPParseExpression().
  199.  */
  200. static void addAllocedTerm(Term *t)
  201. {
  202.     Term **newSpace;
  203.  
  204.     if (!(NumTermsAlloced % STACK_TERMS) && NumTermsAlloced > 0) {
  205.     newSpace = NXZoneMalloc(NXDefaultMallocZone(),
  206.             (NumTermsAlloced + STACK_TERMS) * sizeof(Term *));
  207.     bcopy(TermsAlloced, newSpace, NumTermsAlloced * sizeof(Term *));
  208.     if (NumTermsAlloced > STACK_TERMS)
  209.         NXZoneFree(NXDefaultMallocZone(), TermsAlloced);
  210.     TermsAlloced = newSpace;
  211.     }
  212.     TermsAlloced[NumTermsAlloced++] = t;
  213. }
  214.  
  215. /* a piece of yacc glue called when there is a parse error */
  216. static void yyerror(char *s)
  217. {
  218. }
  219. short yyexca[] ={
  220. -1, 1,
  221.     0, -1,
  222.     -2, 0,
  223.     };
  224. # define YYNPROD 18
  225. # define YYLAST 223
  226. short yyact[]={
  227.  
  228.    3,  25,  14,   3,  17,   4,  13,  26,   4,   5,
  229.   24,  11,   9,  13,  10,  13,  12,   1,  11,   9,
  230.   11,  10,   0,  12,  28,  12,   2,  29,   0,   0,
  231.   15,  16,   0,   0,   0,   0,  18,  19,  20,  21,
  232.   22,  23,   0,   0,  27,   0,   0,   0,   0,   0,
  233.    0,   0,   0,   0,   0,   0,  30,   0,   0,   0,
  234.    0,   0,   0,  14,   0,   0,   0,   0,   0,   0,
  235.   14,   0,  14,   0,   0,   0,   0,   0,   0,   0,
  236.    0,   0,   0,   0,   0,   0,   0,   0,   0,   0,
  237.    0,   0,   0,   0,   0,   0,   0,   0,   0,   0,
  238.    0,   0,   0,   0,   0,   0,   0,   0,   0,   0,
  239.    0,   0,   0,   0,   0,   0,   0,   0,   0,   0,
  240.    0,   0,   0,   0,   0,   0,   0,   0,   0,   0,
  241.    0,   0,   0,   0,   0,   0,   0,   0,   0,   0,
  242.    0,   0,   0,   0,   0,   0,   0,   0,   0,   0,
  243.    0,   0,   0,   0,   0,   0,   0,   0,   0,   0,
  244.    0,   0,   0,   0,   0,   0,   0,   0,   0,   0,
  245.    0,   0,   0,   0,   0,   0,   0,   0,   0,   0,
  246.    0,   0,   0,   0,   0,   0,   0,   0,   0,   0,
  247.    0,   0,   0,   0,   0,   0,   0,   0,   0,   0,
  248.    0,   0,   0,   0,   0,   0,   0,   0,   0,   0,
  249.    0,   0,   0,   0,   0,   0,   0,   6,   7,   8,
  250.    6,   7,   8 };
  251. short yypact[]={
  252.  
  253.  -37,-1000, -24, -37, -37,-1000, -36,-1000,-1000, -37,
  254.  -37, -37, -37, -37, -37, -31, -92, -40, -22, -22,
  255.  -92, -92, -92, -92,-1000,-1000, -17, -24,-1000, -37,
  256.  -24 };
  257. short yypgo[]={
  258.  
  259.    0,  17,  26,   9,   7 };
  260. short yyr1[]={
  261.  
  262.    0,   1,   2,   2,   2,   2,   2,   2,   2,   2,
  263.    2,   2,   2,   2,   3,   3,   4,   4 };
  264. short yyr2[]={
  265.  
  266.    0,   1,   3,   3,   3,   3,   3,   3,   3,   2,
  267.    1,   1,   1,   1,   3,   4,   1,   3 };
  268. short yychk[]={
  269.  
  270. -1000,  -1,  -2,  40,  45,  -3, 257, 258, 259,  43,
  271.   45,  42,  47,  37,  94,  -2,  -2,  40,  -2,  -2,
  272.   -2,  -2,  -2,  -2,  41,  41,  -4,  -2,  41,  44,
  273.   -2 };
  274. short yydef[]={
  275.  
  276.    0,  -2,   1,   0,   0,  10,  11,  12,  13,   0,
  277.    0,   0,   0,   0,   0,   0,   9,   0,   3,   4,
  278.    5,   6,   7,   8,   2,  14,   0,  16,  15,   0,
  279.   17 };
  280. # line 1 "/usr/lib/yaccpar"
  281. #ifndef lint
  282. static char yaccpar_sccsid[] = "@(#)yaccpar    4.1    (Berkeley)    2/11/83";
  283. #endif not lint
  284.  
  285. # define YYFLAG -1000
  286. # define YYERROR goto yyerrlab
  287. # define YYACCEPT return(0)
  288. # define YYABORT return(1)
  289.  
  290. /*    parser for yacc output    */
  291.  
  292. #ifdef YYDEBUG
  293. int yydebug = 0; /* 1 for debugging */
  294. #endif
  295. YYSTYPE yyv[YYMAXDEPTH]; /* where the values are stored */
  296. int yychar = -1; /* current input token number */
  297. int yynerrs = 0;  /* number of errors */
  298. short yyerrflag = 0;  /* error recovery flag */
  299.  
  300. yyparse() {
  301.  
  302.     short yys[YYMAXDEPTH];
  303.     short yyj, yym;
  304.     register YYSTYPE *yypvt;
  305.     register short yystate, *yyps, yyn;
  306.     register YYSTYPE *yypv;
  307.     register short *yyxi;
  308.  
  309.     yystate = 0;
  310.     yychar = -1;
  311.     yynerrs = 0;
  312.     yyerrflag = 0;
  313.     yyps= &yys[-1];
  314.     yypv= &yyv[-1];
  315.  
  316.  yystack:    /* put a state and value onto the stack */
  317.  
  318. #ifdef YYDEBUG
  319.     if( yydebug  ) printf( "state %d, char 0%o\n", yystate, yychar );
  320. #endif
  321.         if( ++yyps>= &yys[YYMAXDEPTH] ) { yyerror( "yacc stack overflow" ); return(1); }
  322.         *yyps = yystate;
  323.         ++yypv;
  324.         *yypv = yyval;
  325.  
  326.  yynewstate:
  327.  
  328.     yyn = yypact[yystate];
  329.  
  330.     if( yyn<= YYFLAG ) goto yydefault; /* simple state */
  331.  
  332.     if( yychar<0 ) if( (yychar=yylex())<0 ) yychar=0;
  333.     if( (yyn += yychar)<0 || yyn >= YYLAST ) goto yydefault;
  334.  
  335.     if( yychk[ yyn=yyact[ yyn ] ] == yychar ){ /* valid shift */
  336.         yychar = -1;
  337.         yyval = yylval;
  338.         yystate = yyn;
  339.         if( yyerrflag > 0 ) --yyerrflag;
  340.         goto yystack;
  341.         }
  342.  
  343.  yydefault:
  344.     /* default state action */
  345.  
  346.     if( (yyn=yydef[yystate]) == -2 ) {
  347.         if( yychar<0 ) if( (yychar=yylex())<0 ) yychar = 0;
  348.         /* look through exception table */
  349.  
  350.         for( yyxi=yyexca; (*yyxi!= (-1)) || (yyxi[1]!=yystate) ; yyxi += 2 ) ; /* VOID */
  351.  
  352.         while( *(yyxi+=2) >= 0 ){
  353.             if( *yyxi == yychar ) break;
  354.             }
  355.         if( (yyn = yyxi[1]) < 0 ) return(0);   /* accept */
  356.         }
  357.  
  358.     if( yyn == 0 ){ /* error */
  359.         /* error ... attempt to resume parsing */
  360.  
  361.         switch( yyerrflag ){
  362.  
  363.         case 0:   /* brand new error */
  364.  
  365.             yyerror( "syntax error" );
  366.         yyerrlab:
  367.             ++yynerrs;
  368.  
  369.         case 1:
  370.         case 2: /* incompletely recovered error ... try again */
  371.  
  372.             yyerrflag = 3;
  373.  
  374.             /* find a state where "error" is a legal shift action */
  375.  
  376.             while ( yyps >= yys ) {
  377.                yyn = yypact[*yyps] + YYERRCODE;
  378.                if( yyn>= 0 && yyn < YYLAST && yychk[yyact[yyn]] == YYERRCODE ){
  379.                   yystate = yyact[yyn];  /* simulate a shift of "error" */
  380.                   goto yystack;
  381.                   }
  382.                yyn = yypact[*yyps];
  383.  
  384.                /* the current yyps has no shift onn "error", pop stack */
  385.  
  386. #ifdef YYDEBUG
  387.                if( yydebug ) printf( "error recovery pops state %d, uncovers %d\n", *yyps, yyps[-1] );
  388. #endif
  389.                --yyps;
  390.                --yypv;
  391.                }
  392.  
  393.             /* there is no state on the stack with an error shift ... abort */
  394.  
  395.     yyabort:
  396.             return(1);
  397.  
  398.  
  399.         case 3:  /* no shift yet; clobber input char */
  400.  
  401. #ifdef YYDEBUG
  402.             if( yydebug ) printf( "error recovery discards char %d\n", yychar );
  403. #endif
  404.  
  405.             if( yychar == 0 ) goto yyabort; /* don't discard EOF, quit */
  406.             yychar = -1;
  407.             goto yynewstate;   /* try again in the same state */
  408.  
  409.             }
  410.  
  411.         }
  412.  
  413.     /* reduction by production yyn */
  414.  
  415. #ifdef YYDEBUG
  416.         if( yydebug ) printf("reduce %d\n",yyn);
  417. #endif
  418.         yyps -= yyr2[yyn];
  419.         yypvt = yypv;
  420.         yypv -= yyr2[yyn];
  421.         yyval = yypv[1];
  422.         yym=yyn;
  423.             /* consult goto table to find next state */
  424.         yyn = yyr1[yyn];
  425.         yyj = yypgo[yyn] + *yyps + 1;
  426.         if( yyj>=YYLAST || yychk[ yystate = yyact[yyj] ] != -yyn ) yystate = yyact[yypgo[yyn]];
  427.         switch(yym){
  428.             
  429. case 1:
  430. # line 72 "expr.ym"
  431. { CompleteExpr = yyval.node; } break;
  432. case 2:
  433. # line 76 "expr.ym"
  434. { yyval.node = yypvt[-1].node; } break;
  435. case 3:
  436. # line 78 "expr.ym"
  437. { yyval.node = allocBinaryOpTerm('+', yypvt[-2].node, yypvt[-0].node); } break;
  438. case 4:
  439. # line 80 "expr.ym"
  440. { yyval.node = allocBinaryOpTerm('-', yypvt[-2].node, yypvt[-0].node); } break;
  441. case 5:
  442. # line 82 "expr.ym"
  443. { yyval.node = allocBinaryOpTerm('*', yypvt[-2].node, yypvt[-0].node); } break;
  444. case 6:
  445. # line 84 "expr.ym"
  446. { yyval.node = allocBinaryOpTerm('/', yypvt[-2].node, yypvt[-0].node); } break;
  447. case 7:
  448. # line 86 "expr.ym"
  449. { yyval.node = allocBinaryOpTerm('%', yypvt[-2].node, yypvt[-0].node); } break;
  450. case 8:
  451. # line 88 "expr.ym"
  452. { yyval.node = allocBinaryOpTerm('^', yypvt[-2].node, yypvt[-0].node); } break;
  453. case 9:
  454. # line 90 "expr.ym"
  455. { yyval.node = _EXPAllocTerm(ParseZone, binOpTerm, 1, yypvt[-0].node); 
  456.           yyval.node->data.binOp.op = '-';
  457.         } break;
  458. case 11:
  459. # line 95 "expr.ym"
  460. { yyval.node = allocVarTerm(yypvt[-0].string); } break;
  461. case 12:
  462. # line 97 "expr.ym"
  463. { yyval.node = allocConstantTerm(yypvt[-0].real, NO); } break;
  464. case 13:
  465. # line 99 "expr.ym"
  466. { yyval.node = allocConstantTerm(yypvt[-0].integer, YES); } break;
  467. case 14:
  468. # line 103 "expr.ym"
  469. { yyval.node = allocFuncTerm(yypvt[-2].string, NULL); } break;
  470. case 15:
  471. # line 105 "expr.ym"
  472. { yyval.node = allocFuncTerm(yypvt[-3].string, yypvt[-1].list); } break;
  473. case 16:
  474. # line 109 "expr.ym"
  475. { yyval.list = NXZoneMalloc(NXDefaultMallocZone(), sizeof(TermList));
  476.           yyval.list->terms[0] = yypvt[-0].node;
  477.           yyval.list->num = 1;
  478.         } break;
  479. case 17:
  480. # line 114 "expr.ym"
  481. { yyval.list = NXZoneRealloc(NXDefaultMallocZone(), yypvt[-2].list,
  482.                 sizeof(TermList) + yypvt[-2].list->num*sizeof(Term *));
  483.           yyval.list->terms[yyval.list->num] = yypvt[-0].node;
  484.           yyval.list->num++;
  485.         } break;
  486. # line 148 "/usr/lib/yaccpar"
  487.  
  488.         }
  489.         goto yystack;  /* stack new state and value */
  490.  
  491.     }
  492.